package com.axzh.interview.algorithm;

/**
 * 背包问题
 * @author Administrator
 *
 */
public class KnapsackProblem {

	public static void main(String[] args) {
		int[] weight = {1,2,5,6,7};
		int[] value={1,6,18,22,28};
		KnapsackProblem.knapsack(value, weight, 11);
	}
	
	public static void knapsack(int[] v, int[] w, int weight) {
		int[][] result = new int[w.length+1][weight+1];
		for(int i=0;i<w.length+1;i++) {
			result[i][0]=0;
		}
		for(int i=0;i<weight+1;i++) {
			result[0][i]=0;
		}
		for(int i=1;i<w.length+1;i++) {
			for(int j=1;j<weight+1;j++) {
				if(w[i-1]>j) {
					result[i][j]=result[i-1][j];
				}else {
					result[i][j]=Math.max(result[i-1][j], v[i-1]+result[i-1][j-w[i-1]]);
				}
			}
		}
		for(int[] a:result) {
			for(int b:a) {
				System.out.print(b+"\t");
			}
			System.out.println();
		}
	}

}
